import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

class LRUCache {
    int capacity;
    Map<Integer, Integer> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new LinkedHashMap<>(capacity);
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            int value = map.get(key);
            map.remove(key);
            map.put(key, value);
            return map.get(key);
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.remove(key);
            map.put(key,value);
        }else {
            if(capacity<1){
                Iterator<Integer> iterator = map.keySet().iterator();
                Integer next = iterator.next();
                map.remove(next);
                capacity++;
            }
            map.put(key,value);
            capacity--;
        }
    }
}